home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / lysrc.zip / LEXPOS.PAS < prev    next >
Pascal/Delphi Source File  |  1993-01-24  |  4KB  |  139 lines
  1.  
  2. unit LexPos;
  3.  
  4. (* 2-5-91 AG *)
  5.  
  6. (* Copyright (c) 1990,91 by Albert Graef, Schillerstr. 18,
  7.    6509 Schornsheim/Germany
  8.    All rights reserved *)
  9.  
  10. interface
  11.  
  12. uses LexBase, LexTables;
  13.  
  14. (* Construct the position table, as well as first position sets.
  15.  
  16.    The position table stores symbol positions in regular expressions of
  17.    the Lex grammar. It also allows to store the corresponding first
  18.    and follow sets. By this means, the position table represents an eps-
  19.    free nondeterministic automaton for the regular expressions of the
  20.    Lex grammar (cf. Aho/Sethi/Ullman, Compilers : Principles, Techniques
  21.    and Tools, 1986, Section 3.9, on constructing NFA's from regular
  22.    expressions using position tables). *)
  23.  
  24. procedure addExpr(r : RegExpr; var FIRST : IntSet);
  25.   (* Add the positions in r to the position table, and return the set of
  26.      first positions of r. *)
  27.  
  28. implementation
  29.  
  30. procedure eval(r : RegExpr;
  31.                var FIRST, LAST : IntSet;
  32.                var nullable : Boolean);
  33.   (* Evaluates the expression r, adding the positions in r to the position
  34.      table and assigning FIRST, LAST and FOLLOW sets accordingly (cf. Aho/
  35.      Sethi/Ullman, Compilers : Principles, Techniques and Tools, Section 3.9).
  36.      Returns:
  37.      - FIRST: the set of first positions in r
  38.      - LAST: the set of last positions in r
  39.      - nullable: denotes whether the r is nullable (i.e. is matched by the
  40.        empty string). *)
  41.   var
  42.     c : Char;
  43.     str : StrPtr;
  44.     cc : CClassPtr;
  45.     rule, pos : Integer;
  46.     r1, r2 : RegExpr;
  47.     FIRST1, LAST1 : IntSet;
  48.     nullable1 : Boolean;
  49.     i : integer;
  50.   begin
  51.     if is_epsExpr(r) then
  52.       begin
  53.         empty(FIRST); empty(LAST);
  54.         nullable := true
  55.       end
  56.     else if is_markExpr(r, rule, pos) then
  57.       begin
  58.         addMarkPos(rule, pos);
  59.         singleton(FIRST, n_pos); singleton(LAST, n_pos);
  60.         nullable := true
  61.       end
  62.     else if is_charExpr(r, c) then
  63.       begin
  64.         addCharPos(c);
  65.         singleton(FIRST, n_pos); singleton(LAST, n_pos);
  66.         nullable := false
  67.       end
  68.     else if is_strExpr(r, str) then
  69.       if length(str^)=0 then
  70.         (* empty string is treated as empty expression *)
  71.         begin
  72.           empty(FIRST); empty(LAST);
  73.           nullable := true
  74.         end
  75.       else
  76.         begin
  77.           addCharPos(str^[1]);
  78.           singleton(FIRST, n_pos);
  79.           for i := 2 to length(str^) do
  80.             begin
  81.               addCharPos(str^[i]);
  82.               singleton(pos_table^[pred(n_pos)].follow_pos^, n_pos);
  83.             end;
  84.           singleton(LAST, n_pos);
  85.           nullable := false
  86.         end
  87.     else if is_CClassExpr(r, cc) then
  88.       begin
  89.         addCClassPos(cc);
  90.         singleton(FIRST, n_pos); singleton(LAST, n_pos);
  91.         nullable := false
  92.       end
  93.     else if is_starExpr(r, r1) then
  94.       begin
  95.         eval(r1, FIRST, LAST, nullable);
  96.         for i := 1 to size(LAST) do
  97.           setunion(pos_table^[LAST[i]].follow_pos^, FIRST);
  98.         nullable := true
  99.       end
  100.     else if is_plusExpr(r, r1) then
  101.       begin
  102.         eval(r1, FIRST, LAST, nullable);
  103.         for i := 1 to size(LAST) do
  104.           setunion(pos_table^[LAST[i]].follow_pos^, FIRST);
  105.       end
  106.     else if is_optExpr(r, r1) then
  107.       begin
  108.         eval(r1, FIRST, LAST, nullable);
  109.         nullable := true
  110.       end
  111.     else if is_catExpr(r, r1, r2) then
  112.       begin
  113.         eval(r1, FIRST, LAST1, nullable);
  114.         eval(r2, FIRST1, LAST, nullable1);
  115.         for i := 1 to size(LAST1) do
  116.           setunion(pos_table^[LAST1[i]].follow_pos^, FIRST1);
  117.         if nullable then setunion(FIRST, FIRST1);
  118.         if nullable1 then setunion(LAST, LAST1);
  119.         nullable := nullable and nullable1
  120.       end
  121.     else if is_altExpr(r, r1, r2) then
  122.       begin
  123.         eval(r1, FIRST, LAST, nullable);
  124.         eval(r2, FIRST1, LAST1, nullable1);
  125.         setunion(FIRST, FIRST1);
  126.         setunion(LAST, LAST1);
  127.         nullable := nullable or nullable1
  128.       end
  129.   end(*eval*);
  130.  
  131. procedure addExpr(r : RegExpr; var FIRST : IntSet);
  132.   var LAST : IntSet;
  133.       nullable : Boolean;
  134.   begin
  135.     eval(r, FIRST, LAST, nullable);
  136.   end(*addExpr*);
  137.  
  138. end(*LexPos*).
  139.